
/********************************************************************
CryGame Source File.
Copyright (C), Crytek Studios, 2001-2009.
-------------------------------------------------------------------------
File name:   VolumeNavRegion.h
Version:     v1.00
Description: 

-------------------------------------------------------------------------
History:
- 21:7:2004   14:15 : Created by Kirill Bulatsev

*********************************************************************/

#ifndef __VolumeNavRegion_H__
#define __VolumeNavRegion_H__

#if _MSC_VER > 1000
#pragma once
#endif

#include "IAISystem.h"
#include "NavRegion.h"
#include "Graph.h"
#include "HashSpace.h"

#include "IPhysics.h"

#include <vector>
#include <list>
#include <map>
#include <deque>

class CGraph;

// Danny work in progress - enabling this works for basic navigation, but has problems if the destination
// lies inside an object (e.g. pathfinding to that object) or if the agent is carrying an object. Need
// physics API to change so we can skip entities.
//#define DYNAMIC_3D_NAVIGATION

/// The volume nav region works by loading/calculating individual navigation
/// regions, then stitching these regions together, either after loading
class CVolumeNavRegion : public CNavRegion
{
public:
	CVolumeNavRegion(CGraph* pGraph);
	~CVolumeNavRegion();

	// inherited
	virtual void Clear();

	// inherited
	virtual void BeautifyPath(
		const VectorConstNodeIndices& inPath, TPathPoints& outPath, 
		const Vec3& startPos, const Vec3& startDir, 
		const Vec3& endPos, const Vec3& endDir,
		float radius,
		const AgentMovementAbility& movementAbility,
		const TNavigationBlockers& navigationBlockers);

	// inherited
	virtual void UglifyPath(const VectorConstNodeIndices& inPath, TPathPoints& outPath, 
		const Vec3& startPos, const Vec3& startDir, 
		const Vec3& endPos, const Vec3& endDir);

	// inherited
	virtual unsigned GetEnclosing(const Vec3& pos, float passRadius = 0.f, unsigned startIndex = 0, 
		float range = -1.f, Vec3 * closestValid = 0, bool returnSuspect = false, const char* requesterName = "", bool omitWalkabilityTest = false);

	// inherited
	virtual bool CheckPassability(const Vec3& from, const Vec3& to, float radius, const TNavigationBlockers& navigationBlockers, IAISystem::tNavCapMask ) const;

	// inherited
	virtual float AttemptStraightPath(TPathPoints& pathOut,
		CAStarSolver* m_pAStarSolver,
		const CHeuristic* pHeuristic, 
		const Vec3& start, const Vec3& end,
		unsigned startHintIndex,
		float maxCost,
		const TNavigationBlockers& navigationBlockers,
		bool returnPartialPath);

	/// inherited
	virtual void Update(CCalculationStopper& stopper);

	/// This just reads in the whole 3D navigation
	bool ReadFromFile(const char* szFileName);

	/// Clears and generates 3D navigation based on the list of navigation modifiers that get obtained
	/// from CAISystem. Depending on the calculate flag in the nav mod then the regions will either be 
	/// calculated or loaded from file.

	/// As IAISystem
	//  void Generate3DDebugVoxels();

	/// Gets the graph node from the index stored in the volume data (used during load/save)
	/// Returns 0 if out of bounds
	unsigned GetNodeFromIndex(int index);

	/// Returns true if a path segment capsule would intersect the world (and thus be
	/// a bad path. If intersectAtStart then is true then start represents the start
	/// sphere position. If it's false then it represents the very tip of the 
	/// capsule. Similarly for intersectAtEnd.
	bool PathSegmentWorldIntersection(const Vec3& start,
		const Vec3& end,
		float radius,
		bool intersectAtStart,
		bool intersectAtEnd, 
		EAICollisionEntities aiCollisionEntities) const;

	/// Returns true if the path, defined by a vector of points, would intersect the
	/// world, as in SweptSphereWorldIntersection
	bool DoesPathIntersectWorld(std::vector<Vec3>& path,
		float radius,
		EAICollisionEntities aiCollisionEntities);

	/// VOXEL_VALID means the voxel is in "good" space - i.e. where an alien might
	/// reside. INVALID means it's inside geometry. INDETERMINATE means we couldn't 
	/// work out a result
	enum ECheckVoxelResult { VOXEL_VALID, VOXEL_INVALID };
	/// definitelyValid is set then it should be a location that is definitely valid.
	ECheckVoxelResult	CheckVoxel(const Vec3& pos, const Vec3& definitelyValid) const;

	void DebugDraw() const;
	void DebugDrawConnections() const;
	void DebugDrawConnections(size_t volumeIdx, bool showOtherLabel) const;
	void DebugDrawNavProblems();

	/// see GetNavigableSpacePoint
	void GetNavVolumeSeeds(std::vector<const IEntity*>& navVolumeSeeds);
	/// Finds the best navigable space point for the reference position and puts it in pos. Returns
	/// false if no navigable space entity is found. Entities should be obtained from 
	/// GetNavigableSpaceEntities
	bool GetNavigableSpacePoint(const Vec3& refPos, Vec3& pos, const std::vector<const IEntity*>& entities);

	/// inherited
	virtual void Serialize(TSerialize ser);

	/// inherited
	virtual size_t MemStats();

private:
	class CVolume;
	class CPortal;
	typedef std::vector<CVolume*>   TVolumes;
	typedef std::vector<CPortal>    TPortals;
	typedef std::vector<int>        TPortalIndices;
	typedef std::vector<int>        TVectorInt;
	typedef short                   TVoxelValue;
	typedef unsigned char           TDistanceVoxelValue;
	typedef std::deque<TVoxelValue> TVoxels;
	typedef std::deque<TDistanceVoxelValue> TDistanceVoxels;

	class CVolume
	{
	public:
		const Vec3& Center(const CGraphNodeManager& nodeManager) const { return nodeManager.GetNode(m_graphNodeIndex)->GetPos(); }

		float m_radius;
		TPortalIndices m_portalIndices;
		unsigned m_graphNodeIndex;
		float m_distanceToGeometry; ///< approximate distance to the nearest geometry

		Vec3 GetConnectionPoint(const CVolumeNavRegion* pVolumeNavRegion, const CVolume* pOtherVolume) const;
	};

	// link between volumes
	// it defines portal connecting two volumes
	class CPortal
	{
	public:
		CPortal(CVolume* pVolumeOne, CVolume* pVolumeTwo)
			: m_pVolumeOne(pVolumeOne), m_pVolumeTwo(pVolumeTwo), m_passRadius(100.f) {}
		bool IsConnecting(const CVolume* pVolumeOne, const CVolume* pVolumeTwo) const;

		CVolume* m_pVolumeOne;
		CVolume* m_pVolumeTwo;
		Vec3 m_passPoint;
		float m_passRadius;
	};

	// used during generation
	struct SVoxelAABox
	{
		Vec3 vBottomLeftCorner;
		TVoxels voxels;
		TDistanceVoxels distanceVoxels;
		float size;
		Vec3i dim;
	};

	struct SRegionData
	{
		/// These are derived immediately from the input data
		string name;
		const struct SpecialArea* sa;
		AABB aabb;
		float volumeRadius;

		TVolumes volumes;
		TPortals portals;

		SVoxelAABox voxelAABox;

		// Used when stitching - all the volumes at the edge
		TVolumes edgeVolumes;
	};

	TVoxelValue GetVoxelValue(const SVoxelAABox& voxelData, int xIdx, int yIdx, int zIdx) const;

	Vec3 GetConnectionPoint(TVolumes& volumes, TPortals& portals, int volumeIdx1, int volumeIdx2) const;
	CVolume* GetVolume(TVolumes& volumes, int volumeIdx) const;
	int GetVolumeIdx(const TVolumes& volumes, const CVolume* pVolume) const;
	CPortal* GetPortal(TPortals& portals, int portalIdx);
	const CPortal* GetPortal(const TPortals& portals, int portalIdx) const;
	int GetPortalIdx(const TPortals& portals, const CPortal* pPortal) const;

	CVolume* CreateVolume(TVolumes& volumes, const Vec3& pos, float radius, float distanceToGeometry);

	void LoadRegion(const char* szLevel, const char* szMission, SRegionData& regionData);

	bool LoadNavigation(TVolumes& volumes, TPortals& portals, CCryFile& cryFile);

	bool LoadPortal(TVolumes& volumes, TPortals& portals, CCryFile& cryFile);

	bool LoadVolume(TVolumes& volumes, CCryFile& cryFile);

	//============ end of generation code ====================

	/// Sweeps a sphere from volume to pos and returns the sphere position at the intersection time
	Vec3 CalcClosestPointFromVolumeToPos(const CVolume &volume, const Vec3& pos, float passRadius) const;

	/// Checks if pos lies within vol. if extra > 0 then the test is made less strict by that amount
	/// in the radial direction. 
	bool IsPointInVolume(const CVolume& vol, const Vec3& pos, float extra = 0.f) const;

	/// Checks if there is a clear line of navigation inside the nav volume, for the current path requester
	bool CheckVolumeNavLine(const Vec3& start,const Vec3& end) const;

	bool AreAllLinksBlocked(unsigned nodeIndex, float passRadius);

	CGraph* m_pGraph;

	// here is the environment representation
	AABB m_AABB;
	TVolumes m_volumes;
	TPortals m_portals;

	float m_maxVolumeRadius;

	/// portal index that was last checked for gravity streams
	unsigned m_lastGravityPortalIndex;

	/// Only gets populated during 3D generation if ai_DebugDrawVolumeVoxels is set
	/// Note - memory lock fails if it's a std::vector (std::vector of std::deque bad?)
	typedef std::list<SVoxelAABox> TDebugVoxels;
	TDebugVoxels m_debugVoxels;
};


#endif __VolumeNavRegion_H__
